package Leetcode.DayTest;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/10/6 10:29
 * @Description: 周赛418
 */

public class Test_418 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 4};
        long[] queries = {0, 2, 2};
        int[] result = gcdValues(nums, queries);
        System.out.println(Arrays.toString(result)); // 输出: [1, 2, 2]

        int[] nums2 = {4, 4, 2, 1};
        long[] queries2 = {5, 3, 1, 0};
        int[] result2 = gcdValues(nums2, queries2);
        System.out.println(Arrays.toString(result2)); // 输出: [4, 2, 1, 1]
    }
    /**
     * 给你一个长度为n的整数数组 nums 和一个整数数组 queries
     * gcdPairs 表示数组 nums 中所有满足 0 <=i<j<n 的数对(nums[i]，nums[j])的 最大公约数 升序 排列构成的数
     * 组.
     * 对于每个査询 queries[i]，你需要找到 gcdPairs 中下标为 queries[i]的元素。
     * 请你返回-个整数数组 answer
     * 其中 answer[i]是 gcdPairs [queries[i]] 的值,
     * gcd(a，b)表示a和b的最大公约数，
     * 示例 1:
     * 输入:nums =[2,3,4]，queries = [0,2,2]
     * 输出:[1,2,2]
     * 解释:
     * gcdPairs = [gcd(nums[0], nums[1]), gcd(nums[0], nums[2]), gcd(nums[1], nums[2])]= [1,2, 1]
     * 升序排序后得到 gcdPairs=[1，1，2]。
     * 所以答案为 [gcdPairs [queries [0]],gcdPairs [queries[1]],gcdPairs [queries [2]]]= [1,2,2]。
     * 示例 2:
     * 输入:nums =[4,4,2,1]，queries =[5,3,1,0]
     * 输出:[4,2,1,1]
     * 解释:
     * gcdPairs 升序排序后得到[1，1，1，2 ,2,4]
     *
     */
    public static int[] gcdValues(int[] nums, long[] queries) {
        int maxVal = Arrays.stream(nums).max().getAsInt();
        int[] gcdCount = new int[maxVal + 1];

        Arrays.sort(nums);

        // 计算所有数对的GCD，并更新计数数组
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int gcdVal = gcd(nums[i], nums[j]);
                gcdCount[gcdVal]++;
            }
        }

        // 根据计数数组构造排序后的GCD数组
        int[] sortedGcds = new int[nums.length * (nums.length - 1) / 2];
        int index = 0;
        for (int i = 1; i <= maxVal; i++) {
            for (int j = 0; j < gcdCount[i]; j++) {
                sortedGcds[index++] = i;
            }
        }
        System.out.println(Arrays.toString(sortedGcds));
        // 根据queries返回结果
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = sortedGcds[(int) queries[i]];
        }
        return answer;
    }

    // 计算两个数的最大公约数
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    /**
     * 给你一个维整数数组 edges，
     * 它表示一棵 n 个节点的 无向 图，其中 edges [i] = [ui，v;] 表示节点 山 和 vi 之间有一条边。
     * 请你构造一个二维矩阵，满足以下条件:
     * 矩阵中每个格子 --对应图中 0到 n-1的所有节点。
     * 矩阵中两个格子相邻(横 的或者 竖 的)当且仅当 它们对应的节点在 edges 中有边连接。
     * 题目保证 edges 可以构造一个满足上述条件的二维矩阵。
     * 请你返回一个符合上述要求的二维整数数组，如果存在多种答案，返回任意一个。
     * 示例 1:
     * 输入:n=4,edges =[[0,1],[0,2],[1,3]，[2,3]]
     * 输出:[[3,1]，[2,0]]
     */
    public int[][] constructGridLayout(int n, int[][] edges) {
        return null;
    }


    /**
     * 你正在维护一个项目，该项目有n个方法，编号从0到n-
     * 给你两个整数n和k，以及一个二维整数数组invocations，
     * 其中 invocations[i]= [ai，bi] 表示方法 ai 调用了
     * 方法 bi。
     * 已知如果方法 k 存在一个已知的 bug。那么方法 k 以及它直接或间接调用的任何方法
     * 都被视为 可疑方法，我们需要从项目中移除这些方法。
     * 只有当一组方法没有被这组之外的任何方法调用时，这组方法才能被移除。
     * 返回一个数组，包含移除所有 可疑方法 后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除 所有 可疑方法
     * 则 不 移除任何方法。
     * 示例 1:
     * 输入:n=4，k=1,invocations =[[1,2],[0,1],[3,2]]
     * 输出:[0,1,2,3]
     *
     * 创建一个邻接表来表示方法之间的调用关系。
     * 使用深度优先搜索（DFS）或广度优先搜索（BFS）从方法 k 开始，找到所有直接或间接被调用的方法，并将这些方法标记为可疑。
     * 检查每个可疑方法是否被其他非可疑方法调用。如果被调用，则无法移除所有可疑方法。
     * 如果所有可疑方法都可以被移除，那么从所有方法中移除这些可疑方法，并返回剩余的方法列表。
     *
     * todo:这个地方的话，是不是可以用这个思想做一个代码bug调试器？能够返回可能所有出现bug的服务id，就可以减轻人为寻找长链路下的调用了
     * （更深层次一点的话是不是可以同一个项目下的不同方法间的调用也可以判断呢？）
     * 但是中间实现的话需要定义一下什么情况下叫做不符合预期，这个步骤需要人为的输入参数或者AI输入？
     */
    public List<Integer> remainingMethods(int n, int k, int[][] invocations) {
        List<Integer> vertices = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            vertices.add(i); // 假设顶点编号从0开始到n-1
        }

        // 创建邻接表
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] invocation : invocations) {
            graph.computeIfAbsent(invocation[0], v -> new ArrayList<>()).add(invocation[1]);
        }

        // 使用 DFS 找到所有可疑方法
        //所有可能受到方法 k bug 影响的方法的集合
        Set<Integer> suspiciousMethods = new HashSet<>();
        dfs(k, graph, suspiciousMethods);

        // 检查是否有任何可疑方法被非可疑方法调用
        for (int[] invocation : invocations) {
            if (!suspiciousMethods.contains(invocation[0]) && suspiciousMethods.contains(invocation[1])) {
                // 如果可疑方法被非可疑方法调用，则返回所有方法
                return vertices;
            }
        }

        // 移除所有可疑方法，并返回剩余的方法
        List<Integer> remainingMethods = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!suspiciousMethods.contains(i)) {
                remainingMethods.add(i);
            }
        }
        return remainingMethods;
    }

    private void dfs(int method, Map<Integer, List<Integer>> graph, Set<Integer> suspiciousMethods) {
        if (suspiciousMethods.contains(method)) {
            return;
        }
        suspiciousMethods.add(method);
        List<Integer> calledMethods = graph.get(method);
        if (calledMethods != null) {
            for (int calledMethod : calledMethods) {
                dfs(calledMethod, graph, suspiciousMethods);
            }
        }
    }


    /**
     * 给你一个长度为 3 的整数数组 nums 。
     * 现以某种顺序 连接 数组 nums 中所有元素的 二进制表示 ，请你返回可以由这种方法形成的 最大 数值.
     * 注意 任何数字的二进制表示 不含 前导零。
     * 示例 1:
     * 输入: nums = [1,2,3]
     * 输出: 30
     * 解释:
     * 按照顺序[3，1，2]连接数字的二进制表示，
     * 得到结果 “11110”，
     * 这是 30 的二进制表示。
     *
     *
     */
    public int maxGoodNumber(int[] nums) {
        // 将整数转换为二进制字符串
        String[] binaryStrings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            binaryStrings[i] = Integer.toBinaryString(nums[i]);
        }
        System.out.println(Arrays.toString(binaryStrings));

        // 按照二进制字符串的字典序从大到小排序
        Arrays.sort(binaryStrings, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                return (b + a).compareTo(a + b);
            }
        });

        // 连接排序后的二进制字符串
        String resultBinaryString = String.join("", binaryStrings);

        // 将二进制字符串转换回整数
        return Integer.parseInt(resultBinaryString, 2);
    }
}
